﻿// --------------------------------------------------------------------------------------------------------------------
// <copyright file="NaturalOrderComparer.cs" company="Mark Christian D. Menchavez">
//   Licensed under the MIT license: http://www.opensource.org/licenses/mit-license.php
// </copyright>
// --------------------------------------------------------------------------------------------------------------------

namespace MCDM
{
    using System.Collections.Generic;

    /// <summary>
    /// Implements a string comparison operation that uses natural order comparison rules.
    /// </summary>
    public class NaturalOrderComparer : IComparer<string>
    {
        /// <summary>
        /// Compares two strings and returns a value indicating whether one is less than, equal to, or greater than the other.
        /// </summary>
        /// <param name="x">
        /// The first string to compare.
        /// </param>
        /// <param name="y">
        /// The second string to compare.
        /// </param>
        /// <returns>
        /// Value Condition 
        ///   Less than zero      x is less than y.
        ///   Zero                x equals y.
        ///   Greater than zero   x is greater than y.
        /// </returns>
        public int Compare(string x, string y)
        {
            if (x == null && y == null)
            {
                return 0;
            }

            if (x == null)
            {
                return -1;
            }

            if (y == null)
            {
                return 1;
            }

            var a = x.ToUpperInvariant();
            var b = y.ToUpperInvariant();

            int ia = 0, ib = 0;

            while (true)
            {
                var nza = 0;
                var nzb = 0;
                var ca = CharAt(a, ia);
                var cb = CharAt(b, ib);

                while (char.IsWhiteSpace(ca) || ca == '0')
                {
                    if (ca == '0')
                    {
                        nza++;
                    }
                    else
                    {
                        nza = 0;
                    }

                    ca = CharAt(a, ++ia);
                }

                while (char.IsWhiteSpace(cb) || cb == '0')
                {
                    if (cb == '0')
                    {
                        nzb++;
                    }
                    else
                    {
                        nzb = 0;
                    }

                    cb = CharAt(b, ++ib);
                }

                if (char.IsDigit(ca) && char.IsDigit(cb))
                {
                    int result;
                    if ((result = CompareNaturally(a.Substring(ia), b.Substring(ib))) != 0)
                    {
                        return result;
                    }
                }

                if (ca == 0 && cb == 0)
                {
                    return nza - nzb;
                }

                if (ca < cb)
                {
                    return -1;
                }

                if (ca > cb)
                {
                    return +1;
                }

                ++ia;
                ++ib;
            }
        }

        private static char CharAt(string value, int index)
        {
            if (index >= value.Length)
            {
                return (char)0;
            }

            return value[index];
        }

        private static int CompareNaturally(string x, string y)
        {
            x = x.ToUpperInvariant();
            y = y.ToUpperInvariant();

            var bias = 0;
            var ia = 0;
            var ib = 0;

            for (;; ia++, ib++)
            {
                var ca = CharAt(x, ia);
                var cb = CharAt(y, ib);

                if (!char.IsDigit(ca) && !char.IsDigit(cb))
                {
                    return bias;
                }

                if (!char.IsDigit(ca))
                {
                    return -1;
                }

                if (!char.IsDigit(cb))
                {
                    return +1;
                }

                if (ca < cb)
                {
                    if (bias == 0)
                    {
                        bias = -1;
                    }
                }
                else if (ca > cb)
                {
                    if (bias == 0)
                    {
                        bias = +1;
                    }
                }
            }
        }
    }
}
